//LCR 098. 不同路径
class Solution {
public:
    int uniquePaths(int m, int n) {
        //1.创建dp表
        //2.初始化
        //3.填表
        //4.返回值
        vector<vector<int>> dp(m+1,vector<int>(n+1)); //这里需要额外的申请一部分空间，方便后续填表
        dp[0][1]=1; 

        for(int i=1;i<=m;i++)   //从上往下
        {
            for(int j=1;j<=n;j++) //从左往右
            {
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m][n];

    }
};

//63. 不同路径 II
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        const int m = obstacleGrid.size();
        const int n = obstacleGrid[0].size();
        vector<vector<int>>  dp(m+1,vector<int>(n+1));
        dp[0][1]=1;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(obstacleGrid[i-1][j-1]==1)
                {
                    dp[i][j]=0;
                }
                else
                {
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[m][n];
    }
};

//剑指 Offer 47. 礼物的最大价值
class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        const int m=grid.size();
        const int n=grid[0].size();
        vector<vector<int>> dp(m+1,vector<int>(n+1));

        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];
            }
        }
        return dp[m][n];
    }
};

//931. 下降路径最小和
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        const int m = matrix.size();
        const int n=matrix[0].size();

        vector<vector<int>> dp(m+1,vector<int>(n+2));
        for(int i=0;i<=m;i++)
        {
            dp[i][0]=INT_MAX;
            dp[i][n+1]=INT_MAX;
        }
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                int minval = min(dp[i-1][j-1],dp[i-1][j]);
                int maxmin=min(minval,dp[i-1][j+1]);
                dp[i][j]=maxmin+matrix[i-1][j-1]; 
            }
        }
        //计算完成之后找最后一行的最小值
        int res = dp[m][1];
        for(int j=2;j<=n;j++)
        {
            if(dp[m][j]<res)
                res = dp[m][j];
        }
        return res;
    }
};
//64. 最小路径和

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n= grid[0].size();

        vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));
        dp[0][1]=dp[1][0]=0;

        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];
            }
        }
        return dp[m][n];
    }
};

//174. 地下城游戏
//这道题与前面的有所不同，需要逆推，dp[i][j]表示的是到达下一个点所需要的最低血量点数。
class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
            const int m = dungeon.size();
            const int n=dungeon[0].size();
            vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));
            dp[m][n-1]=1;
            dp[m-1][n]=1;
            //从下往上，从右往左遍历
            for(int i=m-1;i>=0;i--)
            {
                for(int j=n-1;j>=0;j--)
                {
                    dp[i][j]=min(dp[i+1][j],dp[i][j+1])-dungeon[i][j];
                    if(dp[i][j]<=0)
                    {
                        dp[i][j]=1;
                    }
                }
            }
            return dp[0][0];
    }
};